/*
 * 4.3
 * Given a sorted (increasing order) array, write an algorithm to create a binary tree with
 * minimal height.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _tree_t {
    int value;
    struct _tree_t *left;
    struct _tree_t *right;
} tree_t;

tree_t *new_tree(int v)
{
    tree_t *t = (tree_t *)malloc(sizeof(tree_t));
    memset(t, 0, sizeof(tree_t));
    t->value = v;
    return t;
}

tree_t *create_tree(int *arr, int left, int right)
{
    if (left > right) {
        return NULL;
    }
    if (left == right) {
        return new_tree(arr[left]);
    }
    int m = left + (right-left)/2;
    tree_t *l = create_tree(arr, left, m-1);
    tree_t *r = create_tree(arr, m+1, right);
    tree_t *t = new_tree(arr[m]);
    t->left = l;
    t->right = r;
    return t;
}

void print_and_free(tree_t *root)
{
    if (!root) {
        return;
    }
    print_and_free(root->left);
    print_and_free(root->right);
    printf("%d ", root->value);
    free(root);
}

int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    tree_t *root = create_tree(arr, 0, sizeof(arr)/sizeof(arr[0])-1);
    /* print and free */
    print_and_free(root);
    printf("\n");
    return 0;
}
